
// 1745.回文串分割IV
class Solution {
public:
    bool checkPartitioning(string s) {
        // 依旧是使用动态规划来实现
        int n = s.size();
        vector<vector<bool>> dp(n,vector<bool>(n));

        for(int i = 0 ; i < n ; i++)        // dp[i][j] 表示[j,i]是否是回文串
        {
            for(int j = 0 ;j <= i ; j++)
            {
                if(s[i] == s[j] && (i == j || j + 1 == i || dp[i-1][j+1]))
                    dp[i][j] = true;
            }
        }
        // 找两刀 , 能将字符串劈开
        for(int i = 1 ; i < n - 1;i++)             // i位置是一刀 , [0 , i-1]
        {
            if(!dp[i-1][0]) continue;
            for(int j = i ; j < n - 1 ;j++)         // j位置是另一刀 , [i , j]
            {
                if(dp[j][i] && dp[n - 1][j + 1])
                     return true;
            }
        }
        return false;
    }
};